package com.future;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

/**
 * Description: 452. 用最少数量的箭引爆气球
 *
 * @author weiruibai.vendor
 * Date: 2023/3/24 10:15
 */
public class Solution_452 {

    private static Solution_452 getInstance() {
        return new Solution_452();
    }

    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>();
        list.add(Integer.MIN_VALUE);
        list.add(Integer.MAX_VALUE);
        list.add(-4);
        list.add(4);
        list.add(400);
        list.sort((o1, o2) -> o1 - o2);
        System.out.println(Integer.MIN_VALUE);
        System.out.println(Integer.MAX_VALUE);
        int[][] points = new int[][]{{10, 16}, {2, 8}, {1, 6}, {7, 12}};
        // points = new int[][]{{1, 2}, {3, 4}, {5, 6}, {7, 8}};
        points = new int[][]{{-2147483646, -2147483645}, {2147483646, 2147483647}};
        System.out.println(getInstance().findMinArrowShots(points));
    }

    /**
     * [[10,16],[2,8],[1,6],[7,12]]
     *
     * @param points
     * @return
     */
    public int findMinArrowShots(int[][] points) {
        List<Info> list = new ArrayList<>();
        for (int i = 0; i < points.length; i++) {
            list.add(new Info(points[i][0], points[i][1]));
        }
        /**
         * 这种方式排序
         * 该用例{{-2147483646, -2147483645}, {2147483646, 2147483647}} 无法通过
         * 原因：
         * o1.start - o2.start当差值比Integer.MIN_VALUE还小时就出现问题，eg:Integer.MIN_VALUE-100<Integer.MIN_VALUE
         * 所以为了解决这个问题，直接用(> < = )比较a和b的大小就行了
         */
        // list.sort((o1, o2) -> o1.start - o2.start);
        /**
         * 改进
         */
        list.sort((o1, o2) -> o1.start < o2.start ? -1 : (o1.start == o2.start ? 0 : 1));
        /**
         * 下面排序才行
         */
        list.sort(Comparator.comparingInt(o -> o.start));
        int ans = 1;
        int end = list.get(0).end;
        for (int i = 0; i < list.size(); i++) {
            Info info = list.get(i);
            if (info.start > end) {
                ans++;
                end = info.end;
            } else {
                end = Math.min(end, info.end);
            }
        }
        return ans;
    }


    class Info {
        public Integer start;
        public Integer end;

        public Info(Integer start, Integer end) {
            this.start = start;
            this.end = end;
        }

        @Override
        public String toString() {
            return "Info{" +
                    "start=" + start +
                    ", end=" + end +
                    '}';
        }
    }
}
